package com.celan.year2023.month02.day26;

public class Solution {
    int[][] wordsDic;
    int[] lettersDic;
    int[] score;
    int n;
    int res = 0;

    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        this.score = score;
        n = words.length;
        //统计words各子集字母出现个数
        wordsDic = new int[n][26];
        for (int i = 0; i < n; i++) {
            for (char c : words[i].toCharArray()) {
                wordsDic[i][c - 'a']++;
            }
        }
        //统计letters字母个数
        lettersDic = new int[26];
        for (char letter : letters) {
            lettersDic[letter - 'a']++;
        }
        this.score = score;

        backTrack(0, 0);
        return res;
    }

    private void backTrack(int idx, int pre) {
        if (idx >= n) {
            res = Math.max(res, pre);
            return;
        }

        int value = 0;
        //当前单词所需字母总数
        int[] dic = wordsDic[idx];
        boolean flag = true;
        //分配
        for (int i = 0; i < 26; i++) {
            lettersDic[i] -= dic[i];
            value += score[i] * dic[i];
            //无法分配
            if (lettersDic[i] < 0) {
                flag = false;
            }
        }
        //如果够分配,则进行计算
        if (flag) {
            res = Math.max(res, pre + value);
            backTrack(idx + 1, pre + value);
        }
        //回溯
        for (int i = 0; i < 26; i++) {
            lettersDic[i] += dic[i];
        }
        //不够分配，跳过当前单词
        backTrack(idx + 1, pre);
    }
}
